package demo10;

/**
 * sort (b merge a)
 */
public class MergeSortDemo2 {
    public MergeSort createMergeSort() {
        return new MergeSort();
    }

    public class MergeSort {
        public void mergeSort(int[] arr) {
            int[] helper = new int[arr.length];
            mergeSort(arr, helper, 0, arr.length - 1);
        }

        /**
         * helper[]
         */
        public void mergeSort(int[] arr, int[] helper, int low, int high) {
            if (low < high) {
                int middle = (low + high) / 2;
                mergeSort(arr, helper, low, middle); // 0~2  (1,4,5)
                mergeSort(arr, helper, middle + 1, high); // 3~5  (2,8,9)
                merge(arr, helper, low, middle, high); //
            }

        }

        public void merge(int[] arr, int[] helper, int low, int middle, int high) {

            for (int i = low; i <= high; i++) {
                    helper[i] = arr[i];
            }

            int current = low;
            int lefthelper = low;
            int rightHelper = middle + 1;

            while (lefthelper <= middle && rightHelper <= high) {

                if (helper[lefthelper] <= helper[rightHelper]) {
                    // left < right
                    arr[current] = helper[lefthelper];
                    lefthelper++;
                } else {
                    // left > right
                    arr[current] = helper[rightHelper];
                    rightHelper++;
                }

                current++;
            }
            int remaning = middle - lefthelper;
            // update remaining ele in the left  side
            for (int i = 0; i <= remaning; i++) {// middle =2 -0 =2
                arr[current + i] = helper[lefthelper + i];
            }

        }

        public int[] mergeAToB(int[] intA, int[] intB) {
            // 6,7,8
            intA[6]=intB[0];
            intA[7]=intB[1];
            intA[8]=intB[2];
            mergeSort(intA);

            return intA;

        }
    }

}
